package com.chao.stucture.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : Rookie
 * @description :
 * @date : 2023/7/11
 */
public class Graph {
    /**
     * 图的顶点数量
     */
    private final int vertices;
    /**
     * 邻接表
     */
    private final LinkedList<Integer>[] adjacencyList;

    public Graph(int v) {
        this.vertices = v;
        adjacencyList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjacencyList[i] = new LinkedList();
    }

    // 添加边
    void addEdge(int v, int w) {
        adjacencyList[v].add(w);
    }

    void dfs(int v) {
        boolean[] visited = new boolean[vertices];
        dfs(v,visited);
    }

    private void dfs(int v,boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (Integer n : adjacencyList[v]) {
            if (!visited[n]) {
                dfs(n,visited);
            }
        }
    }

    void bfs(int v) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            Integer integer = queue.poll();
            System.out.print(integer + " ");

            // 获得当前节点的邻接节点，并遍历
            for (Integer node : adjacencyList[v]) {
                if (!visited[node]) {
                    queue.offer(node);
                    visited[node] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 创建图对象，此例中为有向图
        Graph graph = new Graph(5);

        // 添加边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("DFS遍历(从顶点2开始):");
        graph.dfs(2);

        System.out.println("\nBFS遍历(从顶点2开始):");
        graph.bfs(2);
    }
}
